// #include <stdio.h>
// #include <stdlib.h>
// #include <stdbool.h>
// #include "windows.h"
//
// typedef int DataType;
//
// typedef struct TreeNode {
//     DataType value;
//     struct TreeNode* left;
//     struct TreeNode* right;
// } TreeNode;
//
// typedef struct StackNode {
//     TreeNode* data;
//     struct StackNode* next;
// } StackNode;
//
// typedef struct Stack {
//     StackNode* top;
// } Stack;
//
// // 创建新节点
// TreeNode* CreateNode(DataType value) {
//     TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
//     if (newNode == NULL) {
//         perror("Memory allocation failed");
//         exit(EXIT_FAILURE);
//     }
//     newNode->value = value;
//     newNode->left = newNode->right = NULL;
//     return newNode;
// }
//
// // 插入节点（二叉搜索树规则）
// TreeNode* InsertNode(TreeNode* root, DataType x) {
//     if (root == NULL) {
//         return CreateNode(x);
//     }
//     if (x < root->value) {
//         root->left = InsertNode(root->left, x);
//     } else {
//         root->right = InsertNode(root->right, x);
//     }
//     return root;
// }
//
// // 初始化栈
// void InitStack(Stack* s) {
//     s->top = NULL;
// }
//
// // 判断栈是否为空
// int IsStackEmpty(Stack* s) {
//     return s->top == NULL;
// }
//
// // 入栈
// void Push(Stack* s, TreeNode* node) {
//     StackNode* newNode = (StackNode*)malloc(sizeof(StackNode));
//     if (newNode == NULL) {
//         perror("Memory allocation failed");
//         exit(EXIT_FAILURE);
//     }
//     newNode->data = node;
//     newNode->next = s->top;
//     s->top = newNode;
// }
//
// // 出栈
// TreeNode* Pop(Stack* s) {
//     if (s->top == NULL) {
//         return NULL;
//     }
//     StackNode* temp = s->top;
//     s->top = s->top->next;
//     return temp->data;
// }
//
// // 非递归先序遍历求第k个节点的值
// void PreOrderNonRecursive(TreeNode* root,int k) {
//     Stack s;
//     InitStack(&s);
//     int count=0;
//     Push(&s, root);
//
//     while (!IsStackEmpty(&s)) {
//         TreeNode* node = Pop(&s);
//         count++;
//         if(count==k) {
//             printf("非递归先序遍历的第%d个节点的值为:%d",k,node->value);
//             return;
//         }else {
//             if (node->right) Push(&s, node->right);
//             if (node->left) Push(&s, node->left);
//         }
//     }
//     printf("\n");
// }
//
// //递归先序遍历求第k个节点的值
// void PreOrder(TreeNode* root,int k,int* count) {
//     if(root==NULL||*count>k||k<=0) {
//         return;
//     }
//     (*count)++;
//     if(*count==k) {
//         printf("递归先序遍历第%d个节点的值为:%d",k,root->value);
//         return;
//     }
//     PreOrder(root->left,k,count);
//     PreOrder(root->right,k,count);
// }
//
// // 释放内存
// void FreeTree(TreeNode* root) {
//     if (root) {
//         FreeTree(root->left);
//         FreeTree(root->right);
//         free(root);
//     }
// }
//
// int main() {
//     SetConsoleOutputCP(CP_UTF8);
//     TreeNode* root = NULL;
//     int values[] = {50, 30, 70, 20, 40, 60, 80};
//     int length = sizeof(values) / sizeof(values[0]);
//
//     // 构建二叉搜索树
//     for (int i = 0; i < length; i++) {
//         root = InsertNode(root, values[i]);
//     }
//
//     PreOrderNonRecursive(root,3);printf("\n");
//     int count=0;
//     PreOrder(root,3,&count);printf("\n");
//
//     FreeTree(root);
//     return 0;
// }